#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
void SelectSort(int* a, int size)
{
	int begin = 0, end = size - 1;
	while(begin < end)
	{
		int Maxi = begin, Mini = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] > a[Maxi])
				Maxi = i;
			if (a[i] < a[Mini])
				Mini = i;
		}
		Swap(&a[begin], &a[Mini]);
		if (Maxi == begin)
			Maxi = Mini;
		Swap(&a[end], &a[Maxi]);
		begin++; end--;
	}
}

void ADjustDown(int* a,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			++child;
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapSort(int* a, int size)
{
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		ADjustDown(a, size, i);
	}
	int end = size - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		ADjustDown(a, end, 0);
		--end;
	}
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	size_t size = sizeof(arr) / sizeof(arr[0]);
	//SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	HeapSort(arr, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d", arr[i]);
	}
	return 0;
}